#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"

using namespace std;

/*HJJ QQ479287006
 *给你一个二叉树的根节点 root ， 检查它是否轴对称。

 

示例 1：


输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：


输入：root = [1,2,2,null,3,null,3]
输出：false
 

提示：

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/symmetric-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

bool isSymmetricCmp(TreeNode *left, TreeNode *right) {
    if (!left && !right)
        return true;

    //直接返回false
    if ((!left && right) || (left && !right))
        return false;

    if (left && right && left->val != right->val)
        return false;

    if (left && right && left->val == right->val)

        return isSymmetricCmp(left->left, right->right) && isSymmetricCmp(left->right, right->left);


    return false;
}

//因为比较的是两个树 因此得自己写一个函数
bool isSymmetric(TreeNode *root) {
    if (!root)
        return true;

    return isSymmetricCmp(root->left, root->right);

}

//非递归方法

//bool isSymmetric(TreeNode* root) {
//    if (root == NULL) return true;
//    queue<TreeNode*> que;
//    que.push(root->left);   // 将左子树头结点加入队列
//    que.push(root->right);  // 将右子树头结点加入队列
//    while (!que.empty()) {  // 接下来就要判断这这两个树是否相互翻转
//        TreeNode* leftNode = que.front(); que.pop();
//        TreeNode* rightNode = que.front(); que.pop();
//        if (!leftNode && !rightNode) {  // 左节点为空、右节点为空，此时说明是对称的
//            continue;
//        }
//
//        // 左右一个节点不为空，或者都不为空但数值不相同，返回false
//        if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
//            return false;
//        }
//        que.push(leftNode->left);   // 加入左节点左孩子
//        que.push(rightNode->right); // 加入右节点右孩子
//        que.push(leftNode->right);  // 加入左节点右孩子
//        que.push(rightNode->left);  // 加入右节点左孩子
//    }
//    return true;
//}
